#define DEBUG
#include <cstdio>
#include <cstring>
#include <cassert>
#define MAXLENN 100
#define MAXM 5

using namespace std;

class Matrix {
public:
  int n, m, a[1<<MAXM][1<<MAXM];

  void init(int n, int m) {
    this->n = n, this->m = m;
    for (int i=0; i<n; i++) {
      a[i][i] = 1;
    }
  }

  static void mul(Matrix *a, Matrix *b, Matrix *c, int mod) {
    assert(a->m==b->n);
    c->n=a->n, c->m=b->m;
    for (int i=0; i<a->n; i++) {
      for (int j=0; j<b->m; j++) {
	c->a[i][j]=0;
	for (int k=0; k<a->m; k++) {
	  c->a[i][j] = (c->a[i][j]+a->a[i][k]*b->a[k][j]%mod)%mod;
	}
      }
    }
  }
};

class Bignum {
public:
  const int k=10;
  int a[MAXLENN+1];

  void init(char *s) {
    a[0] = strlen(s);
    for (int i=1; i<=a[0]; i++) {
      a[i] = s[a[0]-i]-'0';
    }
  }

  void dec(int x) {
    a[1]-=x;
    for (int i=1; a[i]<0; i++) {
      a[i+1]--;
      a[i] += k;
    }
    a[0] = a[a[0]] ? a[0] : a[0]-1;
  }

  void div(int x) {
    for (int i=a[0]; i>1; i--) {
      a[i-1] = a[i-1]+a[i]%x*k;
      a[i] /= x;
    }
    a[1] /= x;
    a[0] = a[a[0]] ? a[0] : a[0]-1;
  }
};

void genMat(Matrix *a, int m) {
  a->n=a->m=1<<m;
  for (int i=0; i<(1<<m); i++) {
    for (int j=0; j<(1<<m); j++) {
      bool flag=true;
      for (int k=1; flag && k<m; k++) {
	flag = (((i>>k)&1) || ((i>>(k-1))&1) || ((j>>k)&1) || ((j>>(k-1))&1)) && !(((i>>k)&1) && ((i>>(k-1)&1)) && ((j>>k)&1) && ((j>>(k-1))&1));
      }
      a->a[i][j] = flag;
    }
  }
}

void qpowerMat(Matrix *a, Bignum *n, int mod) {
  static Matrix s[2], t[2];
  t[0] = *a;
  s->init(a->n, a->m);
  int i=0, j=0;
  for (; n->a[0]!=1 || n->a[1]>1; n->div(2)) {
    if (n->a[1]&1) {
      Matrix::mul(&s[j%2], &t[i%2], &s[(j+1)%2], mod);
      j++;
    }
    Matrix::mul(&t[i%2], &t[i%2], &t[(i+1)%2], mod);
    i++;
  }
  Matrix::mul(&t[i%2], &s[j%2], a, mod);
}

int main() {
#ifdef DEBUG
  freopen("2.in", "r", stdin);
  freopen("2.out", "w", stdout);
#endif

  char sn[MAXLENN+1];
  int m, p;
  scanf("%s %d %d", sn, &m, &p);
  static Bignum n;
  n.init(sn);

  static Matrix t, a, b;
  t.n=1, t.m=1<<m;
  for (int i=0; i<(1<<m); i++) {
    t.a[0][i]=1;
  }
  genMat(&a, m);
  n.dec(1);
  qpowerMat(&a, &n, p);
  Matrix::mul(&t, &a, &b, p);
  
  int ans=0;
  for (int i=0; i<(1<<m); i++) {
    ans = (ans+b.a[0][i])%p;
  }
  printf("%d", ans);

  fcloseall();
  return 0;
}
